The invention relates to the field of electronic messaging, and specifically to an improved method for routing messages in an electronic messaging system. Electronic messaging is an increasingly popular mode of communications for a wide variety of corporate, government and private sector users. Rapid advances in telecommunications technology have led to equally rapid development of electronic messaging systems to take advantage of new capabilities. Current electronic messaging systems provide the ability to instantaneously transfer information between users anywhere in the world.
An electronic messaging system of a type to which the present invention is directed comprises two major components: a message handling system (MHS) and a message transfer system (MTS). These two components may reside in software executing on a single minicomputer, such as a "DATA GENERAL AVIION" Model 5250 multi-user sewer. Alternatively, separate minicomputers may be dedicated to each component.
The message handling system performs message processing functions, providing users with the ability to compose messages to be sent to others and the ability to read messages received from others. The MHS may include several user agents (UAs) servicing discrete groups of users. Users might typically be grouped by physical location, organization, sub-organization and so on. Each user agent includes software enabling individual users to communicate with the messaging system. Each user has access to a user interface, typically being a personal computer such as an "IBM PS/2 MODEL 70". The user interface communicates with the user agents either directly, via a data line such as RS-232 cable, or indirectly, via a telecommunications line and a modem. An example of a message handling system of this type is the "TELEMAIL" system developed and marketed by "SPRINT INTERNATIONAL".
The message transfer system performs telecommunications switching functions, determining the ideal routing path for a message and transmitting the message along that path. The MTS may include several message transfer agents (MTAs) which communicate with the various user agents of the message handling system. Each MTA is capable of providing message routing functions for one or more user agents, and may be flexibly configured depending on the needs of any particular installation. For example, a message transfer system may contain a first MTA responsible for local delivery of messages (i.e., messages sent between users of the same message handling system) and a second MTA responsible for relaying remote messages (i.e., messages sent between users of two distinct message handling systems). A collection of at least one MTA and zero or more user agents may be referred to as an administration management domain (ADMD). Within an ADMD, user agents obtain message transfer service by interacting with an MTA through submission and delivery procedures. An example of a message transfer system of this type is the "TPX400" system developed and marketed by "SPRINT INTERNATIONAL".
A message transfer system will typically access a routing information data store which associates physical or logical telecommunications paths with particular user addresses. In a typical prior art messaging system, routing information is stored as a hierarchical tree structure containing a number of increasingly-specific levels of classifications, culminating with individual users at the lowest level. For each user defined to the system, the routing information associates an identifier for the telecommunications path that must be followed to send a message to that user.
To illustrate how a message would be composed and routed in an electronic message system configured as above, assume a user wishes to send a message to another user at a remote location serviced by a different electronic messaging system. The user, referred to as a message originator, would compose a message on a user interface using editing functions provided by a user agent. The user agent includes editing routines which ensure the message conforms to the appropriate standards and communications protocols. When the user is satisfied with the message and requests that it be sent, the user agent transmits the message as a digital signal to the message transfer agent servicing that particular user agent. Upon receiving the message, the message transfer agent analyzes the address specified for the recipient and determines the appropriate routing path from the routing information data store. Assuming a routing path exists, the message transfer agent transmits the message along the associated telecommunications line to the electronic messaging system servicing the intended recipient.
While an electronic messaging system capable of routing messages among a group of users in a particular installation or organization clearly has value, one of the challenges for designers of such systems has been providing users with the ability to route messages between different messaging systems. This ability is referred to as "global routing". A primary obstacle to global routing has been the wide variety of messaging systems currently in use, often developed by vendors having their own unique approach to electronic messaging.
To facilitate global routing, the Consultive Committee for International Telegraphy and Telephony (CCITT) developed the X.400 series of recommendations in an effort to standardize electronic messaging systems across different countries and vendors. As part of this effort, messages must be formatted and sent using predefined standards and protocols. A message formatted in compliance with X.400 standards must contain certain items of address information, including an originator/recipient name (O/R name) which includes codes for the originator/recipient user's country, administration management domain, organization and personal name.
Conformance to CCITT standards ensures messages are readily transferable between two electronic messaging systems; however, such conformance limits the flexibility available for configuring messaging systems. One approach to this problem involves maintaining two types of addresses for system users: an internal address related to the administrative configuration of the messaging system, and an external address related to "real world" considerations such as geographic locations and organizational hierarchies. Such an approach is detailed in the U.S. patent application entitled "Method and Apparatus for Global Routing of Electronic Messages", filed by John A. Mullan on the same day as the present application and incorporated herein by reference.
Mere conformance with CCITT standards is insufficient to ensure that an electronic messaging system provides its users with optimal global routing capabilities. While these standards provide a common language for intra- and intersystem communication, they do not address the actual method by which messages are routed within and between electronic messaging systems.
Owing to the vast array of both local and international users that any particular electronic messaging system may serve, a primary emphasis in developing such systems has been the method of routing messages. The merit of any such method is a function of its ability to satisfy the often conflicting requirements of flexibility and speed. In terms of flexibility, a routing method must accommodate large numbers of users and must recognize multiple levels of classifications into which such users fall. Additionally, the routing method should be flexible enough to handle situations where a message is received with an incomplete or invalid address. In terms of speed, the routing method should be able to quickly and accurately determine the optimum telecommunications path for an addressee. Likewise, the routing method should be able to quickly accommodate changes to the routing structure, such as the addition of new subscribers to the messaging system.
As noted above, most known electronic messaging systems store routing information in large, hierarchical tree structures which often require several megabytes of storage. In a typical structure for an electronic messaging system serving international subscribers, the highest level of the tree contains country codes for the various locations. Lower levels contain further breakdowns of the subscribers in each country, such as by organization or other domain-defined attributes. Finally, the lowest level contains the personal names of the individual users.
Hierarchical tree structures of this type are inefficient for a variety of reasons. First and foremost is the fact that such a structure can quickly grow to a very large size, requiring substantial resources in terms of both supporting software and processing time. Second, the large number of nodes and interconnections in these tree structures make modifications cumbersome and time-consuming. Third, the ultimate size of such structures may be unduly constrained by the physical limitations of the hardware on which the electronic messaging system runs.
In addition to problems associated with the tree structure itself, the routing methodology typically used with such a structure is inefficient, generally requiring intricate traversing of many tree branches. Such routing methods often fail to find a defined base or generic address to which a message may be delivered simply because a search has extended too far into the tree trying to find an exact match for the full address specified in a message. For example, where a message address has a valid country code and organization name but an incorrect recipient name, typical search algorithms fail to recognize that the message may nonetheless be deliverable to a general address for the organization. Also, in a worst-case scenario all of the branches of a tree structure must be searched to determine whether a complete match on an address exists.
In light of the limitations of the prior art, there is a need for a method of routing messages in an electronic messaging system that is both efficient and flexible. Furthermore, such a routing method should accommodate a structure for routing information that is simpler than known hierarchical tree structures. These needs and others are satisfied by the method and apparatus of the present invention.